#include"graph.h"
#include"Heap.h"


void Listpush_back(Node* Head, int i, int w)//头插
{
	//创建新节点，并初始化
	Node* newnode = (Node*)malloc(sizeof(Node));
	if (NULL == newnode)
	{
		printf("malloc failed\n");
		exit(-1);
	}
	newnode->next = NULL;
	newnode->i = i;
	newnode->w = w;

	//头插
	newnode->next = Head->next;
	Head->next = newnode;
}

void PrintLength(int* pre, int cur)//打印最短路径
{
	if (cur == -1)
	{
		return;
	}
	PrintLength(pre, pre[cur]);//先去递归前驱节点，再回来打印
	if (pre[cur] == -1)
		printf("S%d", cur);
	else
		printf("->S%d", cur);
}
RN* Dijkstra2(int n,int m,int** road, int start, int end)//最短路算法，Dijkstra算法实现，N*logN(稀疏图)
{

	//首先我们需要初始化邻接表(每一个表使用链表来保存下一条边)，因为road并不是，road只是每条边的信息
	Node* G = (Node*)malloc(sizeof(Node)*n);
	if (NULL == G)
	{
		printf("malloc failed\n");
		exit(-1);
	}
	for (int i = 0; i < n; ++i)//初始化头节点
	{
		G[i].next = NULL;
		G[i].i = -1;
		G[i].w = -1;
	}
	for (int i = 0;i < m;++i)
	{
			int node1 = road[i][0], node2 = road[i][1],w = road[i][2];
			//有向图
			Listpush_back(&G[node1],node2,w);
	}
	RN* r1 = (RN*)malloc(sizeof(RN));
	if (NULL == r1)
	{
		printf("malloc failed\n");
		exit(-1);
	}

	r1->dist = (int*)malloc(sizeof(int)*n);//dist数组存放起点start到每个节点之间的距离，一开始全部初始化为最大值的一半，为什么是一半呢？这里是防止溢出
	if (NULL == r1->dist)
	{
		printf("malloc failed\n");
		exit(-1);
	}
	for (int i = 0; i < n; ++i)
		r1->dist[i] = INT_MAX / 2;

	r1->pre = (int*)malloc(sizeof(int)*n);//dist数组存放起点start到每个节点之间的距离，一开始全部初始化为最大值的一半，为什么是一半呢？这里是防止溢出
	if (NULL == r1->pre)
	{
		printf("malloc failed\n");
		exit(-1);
	}
	for (int i = 0; i < n; ++i)
		r1->pre[i] = -1;
	Heap hp;//创建一个小根堆，来更快的求出每次的最短路径
	HeapInit(&hp);//初始化小根堆

	r1->dist[start] = 0;//start自己到自己的距离是0
	r1->pre[start] = -1;//起点没有上一个节点
	Pair x;//创建一个Pair变量
	x.first = 0;//最短路径
	x.second = start;//下标
	HeapPush(&hp, x);
	while (1)
	{
		int min_i = -1;
		int dis_min = 0;
		if (!HeapEmpty(&hp))
		{
			min_i = HeapTop(&hp).second;
			dis_min = HeapTop(&hp).first;
			HeapPop(&hp);//这个最短路径即将被用来更新其它节点，没有作用了,从优先队列中pop掉
		}
		if (min_i == -1)//求出起点到end的最短路径就满足要求了，退出程序
			break;
		if (dis_min > r1->dist[min_i])//可能出现这种情况，就是这个节点的信息之前就已经存入队列中了，但是再次更新之后没有把旧的信息删除，就会造成这种不匹配的现象，我们跳过这种不合法的情况
			continue;
		//用这个最短路径的点去更新其它的点
		Node* cur = G[min_i].next;//让cur开始遍历min_i顶点指向的边
		while(cur != NULL)
		{
			int newdis = cur->w + r1->dist[min_i];
			if (newdis < r1->dist[cur->i])//如果比我现在的距离要小，就更新距离和上一个节点的下标
			{
				r1->dist[cur->i] = newdis;
				r1->pre[cur->i] = min_i;
				//更新pair的值，并把新的pair插入到小堆中
				x.first = newdis;
				x.second = cur->i;
				HeapPush(&hp, x);
			}
			cur = cur->next;
		}
	}
	HeapDestory(&hp);//释放堆中的空间
	return r1;
}